#
# @lc app=leetcode.cn id=226 lang=python3
#
# [226] 翻转二叉树
#

# @lc code=start
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # # 递归法
        # if not root : return None
        # right = self.invertTree(root.right)
        # left = self.invertTree(root.left)
        # root.left = right
        # root.right = left

        # return root

        # 迭代法(队列实现)
        if not root : return None
        lst = [root]
        while len(lst) != 0:
            cur = lst.pop(0)
            tmp = cur.left
            cur.left = cur.right
            cur.right = tmp
            if cur.left: lst.append(cur.left)
            if cur.right: lst.append(cur.right)

        return root
        

# @lc code=end

